package LeetCode.LC29;

/**
 * 29. 两数相除
 * <p>
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 *
 * @author corn
 * @create 2020-11-03-0:31
 */
public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (divisor == 1) {
            return dividend;
        }
        if (divisor == -1) {
            if (dividend > Integer.MIN_VALUE) return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦
            return Integer.MAX_VALUE;// 是最小的那个，那就返回最大的整数啦
        }
        //使用long防止越界
        long a = dividend;
        long b = divisor;
        //判断结果正负
        int sign = 1;
        if ((a > 0 && b < 0) || (a < 0 && b > 0)) {
            sign = -1;
        }
        //将两数全部变成正数
        a = a > 0 ? a : -a;
        b = b > 0 ? b : -b;
        long res = div(a, b);
        if (sign > 0) {
            //res可能会越界，但是会自动减少到最大数
            return (int) res;
        }
        return (int) -res;
    }
    //简单概括为： 60/8 = (60-32[8<<2])/8 + 4 = (60-32[8<<2]-16[8<<1])/8 + 2 + 4 = 1 + 2 + 4 = 7
    public long div(long a, long b) {
        if (a < b) {
            return 0;
        }
        long count = 1;
        long tab = b;
        while ((tab << 1) <= a) {
            count = count << 1; // 最小解翻倍
            tab = tab << 1; // 当前测试的值也翻倍
        }
        return count + div(a - tab, b);
    }
}
